class Solution(object):
    def zigzagLevelOrder(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        if not root:
            return []
        else:
            node_list = [[root], [root]]
            count = 0
            val_list = []
            while len(node_list[count % 2]) > 0:
                now_node_list = node_list[count % 2]
                length = len(now_node_list)
                count += 1
                next_node_list = []
                now_val_list = []
                for i in range(length):
                    now_val_list.append(now_node_list[i].val)
                    if count % 1 == 1:
                        if now_node_list[length - 1 - i].right:
                            next_node_list.append(now_node_list[length - 1 - i].right)
                        if now_node_list[length - 1 - i].left:
                            next_node_list.append(now_node_list[length - 1 - i].left)
                    else:
                        if now_node_list[length - 1 - i].left:
                            next_node_list.append(now_node_list[length - 1 - i].left)
                        if now_node_list[length - 1 - i].right:
                            next_node_list.append(now_node_list[length - 1 - i].right)
                val_list.append(now_val_list)
                node_list[count % 2] = next_node_list
            return val_list